2D подпись - 2

Максимальная оценка за эту задачу — 40 баллов.

Условие задачи и форматы ввода и вывода полностью совпадают с предыдущей задачей, однако в этой задаче вам необходимо сдать на проверку текстовый файл с ответом на конкретный тест, который вы должны сгенерировать на своем компьютере. Скачать файл со входными данными для этой задачи вы можете нажав на ссылку "Скачать условие задачи" внизу этой страницы (после раздела "Система оценивания").

Во время тура ответ будет проверяться только на соответствие формату, проверка с выставлением баллов будет осуществляться после окончания тура. Статус OK и 0 баллов во время тура означает, что сданный вами файл соответствует формату и будет проверен после тура, в случае других статусов файл не соответствует формату и вам следует проверить и исправить его.

Для проверки подписи документов была придумана новая электронная подпись: таблица размером $n \times m$, в каждой ячейке которой находится цифра 0 или 1. Строки таблицы пронумерованы от $1$ до $n$ сверху вниз, а столбцы — от $1$ до $m$ слева направо. Обозначим символ, расположенный в ячейке на пересечении $i$-й строки и $j$-го столбца как $a_{i, j}$.

Будем называть горизонтальным артефактом любую непустую подстроку любой из строк соответствующей таблицы. Более формально, горизонтальным артефактом называется строка $a_{i, l} a_{i, l + 1} \ldots a_{i, r}$ для любых $1 \le i \le n$ и $1 \le l \le r \le m$.

Аналогично, вертикальным артефактом называется любая непустая подстрока любого из столбцов соответствующей таблицы. Более формально, вертикальным артефактом называется строка $a_{l, j} a_{l + 1, j} \ldots a_{r, j}$ для любых $1 \le l \le r \le n$ и $1 \le j \le m$.

Будем говорить, что строка является артефактом, если она является горизонтальным или вертикальным артефактом.

Проверка подписи осуществляется следующим образом: для набора строк, состоящих из 0 и 1, подсчитывается, сколько строк из этого набора является артефактом.

Напишите программу, которая по данному набору строк составит подпись. Ваша программа получит количество баллов, пропорциональное количеству строк, которые являются артефактами в составленной вами подписи.